﻿//852.山脉数组的峰顶索引
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1])
            {
                left = mid + 1;
            }
            else if (arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1])
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

//162.寻找峰值
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > nums[mid - 1])
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left;
    }
};

//91.解码方法
class Solution {
public:
    int numDecodings(string s)
    {
        int n = s.size();
        vector<int> dp(n);

        if (s[0] != '0')
        {
            dp[0]++;
        }
        if (n == 1) return dp[0];

        if (s[0] != '0' && s[1] != '0')
        {
            dp[1]++;
        }
        if ((s[0] - '0') * 10 + (s[1] - '0') >= 10 && (s[0] - '0') * 10 + (s[1] - '0') <= 26)
        {
            dp[1]++;
        }

        for (int i = 2; i < n; i++)
        {
            if (s[i] != '0')
            {
                dp[i] += dp[i - 1];
            }

            if ((s[i - 1] - '0') * 10 + (s[i] - '0') >= 10 && (s[i - 1] - '0') * 10 + (s[i] - '0') <= 26)
            {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n - 1];
    }
};